package 剑指Offer.简单;

import Entity.ListNode;

/**
 * 示例 1：
 *
 *
 *
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author caihe
 * @date 2022/8/26 9:13
 */
public class _52两个链表的第一个公共节点 {

    /**
     * headA的长度为a，headB的长度为b，公共节点的位置为c
     * a到c的距离为：a - c
     * b到c的距离为：b - c
     * 
     * nodeA遍历完headA后，再遍历headB 到c的距离：a + (b - c)
     * nodeB遍历完headB后，再遍历headA 到c的距离：b + (a - c)
     * 
     * 发现利用这样的公式可以找到第一个公共节点
     *  a + (b - c) = b + (a - c)
     * 
     */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode headNodeA = headA, headNodeB = headB;
        while(headNodeA != headNodeB) {
            // 当前链表遍历完成后需要交换链表进行遍历
            headNodeA = headNodeA == null ? headB : headNodeA.next;
            headNodeB = headNodeB == null ? headA : headNodeB.next;
        }
        return headNodeA;
    }
    
}
